#ifndef HASH_TABLE_H
#define HASH_TABLE_H

#include <stdint.h>
#include <string.h>
#include <stdio.h>
#include <assert.h>

uint64_t ExtractKey(uint64_t keyval) { return (keyval << 4) >> 4; }

uint64_t ExtractVal(uint64_t keyval) { return keyval >> 60; }

// Simple and fast hash table that stores 60-bit => 4 bit mapping.
class HashTable {
 public:
  HashTable(size_t size_log)
      : size_log_(size_log), n_collisions_(0),
      n_inserts_(0), n_lookups_(0) {
    table_ = new uint64_t[1UL << size_log_];
    memset(table_, 0, sizeof(table_[0]) << size_log_);
  }

  ~HashTable() {
    delete [] table_;
  }
  __attribute__((noinline)) uint64_t FindOrInsert(uint64_t key,
                                                  uint64_t value,
                                                  bool do_insert) {
    assert(key < (1ULL << 60));
    assert(value < (1ULL << 4));
    for (int i = 0; i < 64; i++) {
      if (i)
        n_collisions_++;
      else
        n_lookups_++;
      size_t idx = (key + i) & ((1UL << size_log_) - 1);
      uint64_t keyval = table_[idx];
      if (!keyval) {
        if (do_insert) {
          table_[idx] = key | (value << 60);
          n_inserts_++;
        }
        return 0;
      }
      if (ExtractKey(keyval) == key)
        return keyval;
    }
    assert(0);
    return 0;
  }

  bool Insert(uint64_t key, uint64_t value) {
    return FindOrInsert(key, value, true) == 0;
  }

  uint64_t FindKey(uint64_t key) { return FindOrInsert(key, 0, false); }

  uint64_t GetVal(uint64_t key) {
    uint64_t res = FindOrInsert(key, 0, false);
    assert(res);
    return ExtractVal(res);
  }

  size_t n_inserts() const { return n_inserts_; }
  size_t n_lookups() const { return n_lookups_; }
  size_t n_collisions() const { return n_collisions_; }
  size_t size() const { return 1UL << size_log_; }
  uint64_t raw(size_t i) const { return table_[i]; }

 private:
  size_t size_log_;
  size_t n_collisions_, n_inserts_, n_lookups_;
  uint64_t *table_;
};

static void TestHashTable() {
  HashTable *t = new HashTable(10);
  assert(t->Insert(10, 1));
  assert(t->Insert(11, 1));
  assert(t->Insert(12, 1));
  assert(!t->Insert(11, 2));
  assert(t->n_inserts() == 3);
  delete t;
}

#endif  // HASH_TABLE_H
